\subsubsection{Solución elegida}

Nuestra solución al problema es un algoritmo similar al algoritmo de Dijkstra con cola de prioridad para caminos mínimos, para el caso especifico de encontrar un camino entre 2 nodos de un grafo.
El algoritmo comienza por crear un grafo de modo que describa el campo de juego. El grafo resultante es de n x n nodos y los ejes del grafo, son las conexiones de cada nodo a sus adyacentes. 
Un nodo v es adyacente a otro nodo w, si es posible saltar de v a w, o sea si w está en la misma fila o columna que v y la distancia de v a w está entre 1 y la potencia máxima de salto, p+k(siendo p, la potencia de salto del nodo v). 
Para representar estas relaciones de adyacencia, por cada nodo almacenamos, para cada una de sus conexiones, las unidades de potencia(pUsed) y de potencia extra(kUsed) necesarias para realizar la conexión. O sea, que, dados v y w, y sea p=3(potencia de v) y k=2, y tal que w esta a distancia 2 de v, luego en v almacenamos pUsed=2 y kUsed=0. Si en cambio fuese necesario usar 4 unidades de potencia para llegar de v a w, entonces almacenaríamos en v: pUsed=3 y kUsed=1.
Una vez creado el grafo de la forma descripta, buscamos el camino mínimo entre el nodo inicial y final. Para eso implementamos el siguiente algoritmo:

\begin{quote}
\begin{verbatim}

Node es tupla <
    col:int,
    row:int,
    jumpPower:int,
    prevNodes:vector<Arrow*>,
    edgesToNextNodes:vector<Arrow*>,
    jumpsSoFar:vector<int>,
    maxKLeftSoFar:int,
    minJumps:int
>
   
Arrow es tupla <
    toNode:Node*,
    kUsed:int,
    powerUsed:int
>

UnvisitedNode es tupla <
    node:Node*,
    jumpsSoFar:int,
    kLeft:int
>

encontrarCamino(fromNode:Node*, toNode:Node*) : void {
    // Se crea la cola con prioridad
    ColaConPrioridad unvisited = vacia();
    // Se agrega el nodo inicial a la cola de nodos no visitados
    unvisited.push(new UnvisitedNode(fromNode, 0, k)); 
    
    // Se ejecuta el siguiente ciclo, mientras que haya elementos en la cola
    while (unvisited.size() > 0) {
        // Se obtiene una referencia al primer elemento 
        // de la cola de nodos no visitados
        UnvisitedNode* unvisitedNode = unvisited.top(); // O(1)
        
        // Almacenamos referencias directas para facilitar la lectura                       
        Node* node = unvisitedNode->node;
        int jumpsSoFar = unvisitedNode->jumpsSoFar;
        int kLeft = unvisitedNode->kLeft;
        
        // Si el nodo que se removió de la cola es el ultimo nodo, 
        // entonces el algoritmo termina
        if (node == toNode) {            
            break;
        }
        
        // Se saca el primer nodo de la cola
        unvisited.pop(); // O(log(n^2)) = O(log(n))
                
        // Chequeo todos los nodos a los que puedo ir. Si hay nodos a los que puedo 
        // ir con menor cantidad de saltos que los que haya usado para llegar a 
        // ese nodo hasta ahora, entonces a ese nodo le seteo que el nodo anterior 
        // es el actual y con que cantidad de saltos y kLeft llegue. En cambio si hay 
        // nodos a los que ya llegue con menos saltos pero menos kLeft, entonces
        // tambien almaceno en esos nodos el kLeft con el que llego
        // En ambos casos pongo los nodos como no visitados, estableciendo 
        // el rango de kLeft con el que los visite. En el primer caso el rango va a 
        // ser [0, kLeft] y en el segundo va a ser [prevMaxKLeft+1, kLeft], 
        // donde prevMaxKLeft es el kLeft maximo con el que habia llegado
        for (int i=0; i<node->edgesToNextNodes.size(); i++) { // O(4*k)
            Arrow* edgeToNextNode = node->edgesToNextNodes[i];
            Node* nextNode = edgeToNextNode->toNode;
            int kUsed = edgeToNextNode->kUsed;
            int powerUsed = edgeToNextNode->powerUsed;
            int nextNodeKLeft = kLeft - kUsed;
            if(jumpsSoFar + 1 < nextNode->minJumps && nextNodeKLeft >= 0) {
                // como siempre saco los nodos por la minima cantidad de saltos, 
                // solo va a pasar una vez que la minima cantidad de saltos + 1 
                // sea menor a la del nodo siguiente
                nextNode->minJumps = jumpsSoFar + 1;
                nextNode->maxKLeftSoFar = nextNodeKLeft;
                nextNode->jumpsSoFar[nextNodeKLeft] = nextNode->minJumps;
                nextNode->prevNodes[nextNodeKLeft]->toNode = node;
                nextNode->prevNodes[nextNodeKLeft]->powerUsed = powerUsed;
                nextNode->prevNodes[nextNodeKLeft]->kUsed = kUsed;
                unvisited.push(new UnvisitedNode(nextNode, jumpsSoFar+1, 
                		nextNodeKLeft));
            } else if(nextNode->maxKLeftSoFar < nextNodeKLeft && nextNodeKLeft >= 0) {
                nextNode->maxKLeftSoFar = nextNodeKLeft;
                nextNode->jumpsSoFar[nextNodeKLeft] = jumpsSoFar + 1;                
                nextNode->prevNodes[nextNodeKLeft]->toNode = node;
                nextNode->prevNodes[nextNodeKLeft]->powerUsed = powerUsed;
                nextNode->prevNodes[nextNodeKLeft]->kUsed = kUsed;
                unvisited.push(new UnvisitedNode(nextNode, jumpsSoFar+1, 
                		nextNodeKLeft));
            }
        }
     }
 }
\end{verbatim}
\end{quote}

El camino luego queda almacenado en los nodos. Cada nodo posee una lista de nodos previos y para poder retornar el camino hay que hacer un traceback desde el nodo final hacia el inicial. En caso de que no se haya encontrado un camino, luego no se ejecutará el traceback.
La implementación del traceback es la siguiente:

\begin{quote}
\begin{verbatim}

UnvisitedNode es tupla <
    node:Node*,
    kUsed:int,
    powerUsed:int,
    kLeft:int
>

traceback(Node* fromNode, Node* toNode) {
    Node* node = toNode;
    // Cargo los valores desde el nodo final saliendo con la menor cantidad de saltos.
    // Desde los otros nodos puede que la cantidad de saltos que use no sea la minima.
    int jumpsCount = node->minJumps;
    int kLeft = k;
    int lastUsedK = 0;
    int lastPowerUsed = 0;
    int totalUsedK = 0;
    // Recorro hacia atras hasta llegar al nodo inicial
    while(node != NULL && node != fromNode) { // O(k * n^2)
        Node* previousNode = NULL;
        int iKLeft;
        int kUsed = 0;
        int powerUsed = 0;
        // solo busco entre los nodos que tengan suficiente kLeft
        for(iKLeft = totalUsedK; iKLeft<=k; iKLeft++) { // O(k)
            if(node->jumpsSoFar[iKLeft] == jumpsCount) {
                previousNode = node->prevNodes[iKLeft]->toNode;
                kUsed = node->prevNodes[iKLeft]->kUsed;
                powerUsed = node->prevNodes[iKLeft]->powerUsed;
                break;
            }
        }
        if(previousNode) {
            jumpsCount = node->jumpsSoFar[iKLeft] - 1;
            kLeft -= kUsed;
            totalUsedK += kUsed;
            path->push_front(new PathNode(node, lastPowerUsed, lastUsedK, iKLeft)); 
            
            lastUsedK = kUsed;
            lastPowerUsed = powerUsed;
            
            node = previousNode;
            
            if(node == fromNode) {
                path->push_front(new PathNode(node, powerUsed, kUsed, k));
            }
        } else {
            node = NULL;
        }
    }
}
\end{verbatim}
\end{quote}

El traceback comienza desde el último nodo y recorre hacia atrás el camino guardando en un vector los nodos que conforman el camino. 

\subsubsection{Demostración}

Antes de pasar a una explicación más en detalle del algoritmo, veremos un panorama general de su comportamiento.
El algoritmo debe encontrar el camino mínimo entre el nodo inicial y el nodo final. Para encontrar dicho camino, parte desde el nodo inicial y avanza sobre el grafo, usando las conexiones entre los nodos hasta llegar al nodo final. La forma en que avanza es que almacena en una cola los nodos que aun no fueron visitados, pero que están conectados a un nodo que ya fue visitado(el criterio para determinar si un nodo fue visitado o no, se explicará más adelante). De modo que usando un ciclo, va tomando, en cada iteración, un nodo de la cola de no visitados y lo marca como visitado y, al mismo tiempo, agrega los nodos que están conectados a dicho nodo y que aun no fueron visitados a la cola de no visitados. Cuando el algoritmo inicia, no hay ningún nodo conectado a un nodo visitado, entonces se añade el nodo inicial a la lista de no visitados.
El algoritmo almacena información en los nodos cada vez que agrega un nodo a la cola de no visitados. Esta información entre otras cosas, le sirve para determinar si debe agregar un nodo a la cola de no visitados o no. 
El algoritmo funciona porque en cada iteración toma, de la cola de no visitados, el nodo al que entre todos los nodos en la cola, se puede llegar con menor cantidad de saltos hasta el momento, y cuando ese nodo sea el nodo final, el algoritmo termina, porque el primer camino con el que llega al nodo final sera el más corto, o sea el que necesite una menor cantidad de saltos. En caso de que no exista ningún camino, entonces el algoritmo nunca llegará al nodo final y terminará cuando se vacíe la cola.

Veremos ahora que es lo que hace el algoritmo estudiando en mas detalle la implementación.
Para comprender la explicación, es necesario abordar una parte clave del problema, que es que es posible saltar desde un nodo a otro usando unidades de potencia extra, la cual se va gastando a medida que se usa.
Decimos que es clave, pues se puede llegar a un mismo nodo con diferentes unidades restantes de potencia extra, por lo que es necesario considerar esa información para tener en cuenta todos los caminos posibles que se pueden hacer entre los nodos. Previamente mencionamos que un nodo es marcado como visitado luego de que se lo remueve de la cola de no visitados, pero hay que hacer un aclaración al respecto y es que un nodo puede ser visitado a lo sumo k veces. Esto es porque se puede llegar con una cantidad de saltos diferente, por cada valor de unidades de potencia extra restante con que se llega a un nodo, y cada una de esas formas de llegar al nodo, son un camino posible hacia el, que puede llegar a ser parte del camino mínimo. A la vez las unidades de potencia extra definen a que otros nodos se puede saltar.
De modo que es importante entender que en realidad cuando nos referimos a un nodo no visitado, no nos referimos al nodo solo por su fila y columna sino también por la cantidad de potencia extra restante con que se llegó al nodo.

Mencionamos que en los nodos se almacena información cada vez que se los marca como visitados. Esta información es la cantidad de saltos con que se llego al nodo(recordamos que un nodo esta definido por fila, columna, y potencia extra restante), el nodo desde el que se saltó, la potencia usada y la potencia extra usada.
Al guardar esta información en los nodos, vamos construyendo lo posibles caminos entre los nodos partiendo desde el nodo inicial.

El algoritmo comienza creando una cola $unvisited$, cuyos elementos son $UnvisitedNode$. Un $UnvisitedNode$ contiene a puntero a un nodo y además, 2 propiedades, $jumpSoFar$ y $kLeft$. La primer propiedad, $jumpSoFar$ es la cantidad de saltos con que se llegó a ese nodo y $kLeft$ es el k restante con que se llegó a ese nodo(con "llegar a un nodo" nos referimos al momento en que se lo colocó en la cola). Usamos esa información para definir si en el futuro se agregará otros nodos conectados a este nodo. 
La cola $unvisited$ es una cola con prioridad que mantiene los elementos ordenados de forma que el primer elemento contiene siempre al nodo al cual se puede llegar con menor cantidad de saltos. Para comenzar a buscar el camino mínimo, el algoritimo inserta el nodo inicial en la cola. 

Luego se ejecuta un ciclo que en cada iteración toma el primer nodo de la cola, que es aquel al cual entre todos los nodos en la cola se puede llegar con menor cantidad de saltos. Como los nodos en la cola son UnvisitedNode, tenemos por cada nodo, el kLeft y el jumpsSoFar de ese nodo no visitado. 
Ejecutamos un ciclo interno en el que recorremos todos los nodos adyacentes del nodo y evaluamos si los agregaremos a la cola de no visitados o no. Los nodos solo se agregan a la cola de no visitados si cumplen que la cantidad de saltos con que se llegó al nodo actual + 1 es menor a la cantidad de saltos con que se llegó al nodo adyacente hasta el momento. Si no se cumple esto, también pueden ser agregados a la cola de no visitados si la cantidad de puntos de potencia extra restante del nodo actual menos los usados para llegar al nodo actual es mayor a la cantidad de puntos extra con que se ha llegado al nodo adyacente hasta el momento. Esto es porque si se llega a un nodo adyancente con más puntos extra de los que se han usado para llegar hasta el momento a ese nodo, pues entonces es posible usar esos puntos más para saltar a un casillero que antes no era posible saltar y posiblemente encontrar un camino más corto.

El ciclo principal termina cuando se alcanza el nodo final o cuando no hay más nodos en la cola de no visitados. El segundo caso sucede cuando no existe ningún camino posible entre la posición inicial y final.

Una vez obtenido el camino mínimo, este queda guardado en los nodos, pero para poder obtener ese camino de principio a fin, es necesario ejecutar otro algoritmo que hace un traceback desde el nodo final hasta el nodo inicial.

El traceback comienza desde el nodo final. Ejecuta un ciclo en el que tomando un nodo, busca entre los nodos previos de ese nodo alguno que pueda pertenecer a un camino mínimo. Para que un nodo previo pertenezca a un camino mínimo, en la primera iteración se comienza buscando el nodo cuya cantidad de saltos para llegar a él, es 1 menos la cantidad de saltos del camino mínimo(jumpsCount). Luego en cada iteración i, se toma el nodo cuya cantidad de saltos es jumpCount - i - 1. Puede que haya más de un nodo previo que cumpla con esta condición, pues puede haber múltiples caminos mínimos. Además de chequear la cantidad de saltos, también se chequea que los puntos de potencia extra para llegar al nodo anterior sea menor a la potencia restante. De esa manera no devuelve un camino que use mas de k puntos de potencia extra.
Cada vez que se encuentra uno de estos nodos se lo añade al principio de una lista de nodos. Terminado el ciclo, en esa lista se obtiene un camino mínimo ordenado desde el primer nodo hacia el último.



